﻿// 166. 数独.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;

/*
https://www.acwing.com/problem/content/168/
数独 是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。

请编写一个程序填写数独。

输入格式
输入包含多组测试用例。

每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
*/
const int N = 10;
const int M = 1 << N;
string str;

int row[N];
int col[N];
int box[3][3];
int needfilln;


int lowbit(int x)
{
	return x & -x;
}

int ones[M];
int map[M];
void init_m_ones()
{
	for (int i = 0; i < M; ++i)
		for (int j = i; j; j -= lowbit(j))
			ones[i]++;

	for (int i = 0; i < N; i++) 
		map[1 << i] = i;
}

int getone(int x) {
	return ones[x];
}

void init() {
	needfilln = 81;
	for (int i = 0; i < 9; i++) {
		row[i] = (1 << N) - 1; row[i] ^= 1 << 0;
		col[i] = (1 << N) - 1; col[i] ^= 1 << 0;
		box[i / 3][i % 3] = (1 << N) - 1; box[i / 3][i % 3] ^= 1 << 0;
	}

	for (int i = 0; i < str.size(); i++) {
		if (str[i] != '.') {
			int x = i / 9; int y = i % 9;
			int curr = str[i] - '0';
			row[x] ^= 1 << curr;
			col[y] ^= 1 << curr;
			box[x / 3][y / 3] ^= 1 << curr;
			needfilln--;
		}
	}
}


bool dfs() {
	if (needfilln == 0) {
		return true;
	}

	int seln = 9999; int selx = -1; int sely = -1;
	for (int i = 0; i < 81; i++) {
		if (str[i] == '.') {
			int x = i / 9; int y = i % 9;
			if (row[x] == 0 || col[y] == 0 || box[x / 3][y / 3] == 0) return false;
			int t = getone(row[x] & col[y] & box[x / 3][y / 3]);
			if (t == 0) return false;
			
			if (seln > getone(row[x] & col[y] & box[x / 3][y / 3])) {
				seln = getone(row[x] & col[y] & box[x / 3][y / 3]);
				selx = x; sely = y;
			}
		}
	}

	if (selx != -1) {
		int selset = row[selx] & col[sely] & box[selx / 3][sely / 3];
		for (int j = selset; j; j -= lowbit(j)) {
			int t = map[lowbit(j)];
			needfilln--;
			str[selx * 9 + sely] = '0' + t;
			row[selx] -= (1 << t);
			col[sely] -= (1 << t);
			box[selx / 3][sely / 3] -= (1 << t);
			if (dfs() == true) {
				return true;
			}
			row[selx] += (1 << t);
			col[sely] += (1 << t);
			box[selx / 3][sely / 3] += (1 << t);
			str[selx * 9 + sely] = '.';
			needfilln++;
		}
	}

	return false;
}

void solve() {
	if (dfs() == true) {
		cout << str << endl;
		return;
	}

	return;
}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	init_m_ones();
	while (cin >> str) {
		if (str == "end") break;
		init();
		solve();
	}
}
